class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
            return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
            });
        int len = envelopes.size(), p = 0;
        vector<int> ends(len, 0);
        for (int i = 0; i < len; i++)
        {
            int find = position(ends, p, envelopes[i][1]);
            if (find == -1)
                ends[p++] = envelopes[i][1];
            else
                ends[find] = envelopes[i][1];
        }
        return p;
    }

    int position(vector<int>& ends, int len, int k)
    {
        int l = 0, r = len - 1;
        int ans = -1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (ends[mid] >= k)
            {
                ans = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        return ans;
    }
};